package com.techyuan.algorithm.structure.map;

/**
 * @author derek.tian
 */
public class MapUtils {
    /**
     * 除法散列法
     *
     * @param k 待散列
     * @param m 模值
     * @return
     */
    public static int hash1(int k, int m) {
        return k % m;
    }

    /**
     * 乘法散列法
     *
     * @param k 待散列
     * @param m 模值
     * @param A 常数
     * @return
     */
    public static int hash2(int k, int m, float A) {
        return (int) (m * (k * A - (int) (k * A)));
    }

    /**
     * 全域散列法
     *
     * @param k 待散列值
     * @param p 为质数 （所有的k都落在0->p-1区间内）
     * @param m 模值
     * @return
     */
    public static int hash2(int k, int p, int m) {
        int a = 11, b = 13;
        return ((a * k + b) % p) % m;
    }

    //线性探查
    public static int LinerProbing(int k, int m, int i) {
        return (hash1(k, m) + i) % m;
    }

    //二次探查
   public static int QuadraticProbing(int k, int m, int i) {
        int c1 = 17, c2 = 67;

        return (hash1(k, m) + c1 * i + c2 * i * i) % m;
    }

    //双重探查
    public static int DoublefunProbing(int k, int m, int i) {
        return (hash2(k, 17, m) + i * hash1(k, m)) % m;
    }
}
